Convolutional codes are a class of channel codes used to mitigate the effects of channel noise in the transmission of information. The convolutional encoder in a transmitter is a finite-state machine whose operation may be described in terms of a trellis. As it accepts data bits, the convolutional encoder proceeds through a sequence of states and produces output which subsequently is used to define an output sequence of symbols that is transmitted over a (noisy or otherwise impaired channel. The output sequence of symbols corresponds to a path though the trellis that describes that encode operation.
A maximum-likelihood decoder for convolutional codes is known in the art as the Viterbi decoder. The Viterbi decoder determines the output sequence of symbols that was transmitted based on the received corrupted version of the transmitted sequence and knowledge of the code used by the encoder. This sequence corresponds to the "best path", that is, the single path through the trellis having the best so-called path metric. For the Gaussian channel, for example the determination of the output sequence is made by correlating with the received version all possible transmitted code sequences (corresponding to paths through the trellis) and then choosing, as the "maximum likelihood" sequence, the sequence where the correlation is maximum.
As it operates, the Viterbi decoder disregards a number of paths in the trellis and considers only the so-called surviving paths as candidates for the best path. Looking backwards in time or "tracing back", the surviving paths tend to merge into the same predecessor path such that a decision as to the value of an earlier received symbol(s) may be made. For so-called continuous Viterbi decoding, at any point in time a decision is made as to the value of an earlier received symbol by tracing back along the path identified as the best path at that time.
Convolutional codes have been adopted as standards for certain types of communication systems. One example of such a standard is IS-54---a standard for North American digital cellular radio. IS-54 employs a type of convolutional code for sending short messages known in the art as a tailbiting convolutional code. With full tailbiting convolutional codes, a block or frame of information is encoded and communicated in a blockwise manner. The term "tailbiting" refers to the fact that the starting state of the convolutional encoder at the point that it begins to encode a block of information is arranged to coincide with the terminating state of the encoder at the end of that block.
The maximum-likelihood decoder for full tailbiting convolutional codes employs Viterbi decoding. The decoder is aware that the convolutional encoder started and terminated in the same state. However, the identity of that state is data-dependent and thus unknown to the decoder. The optimum maximum-likelihood decoding for tailbiting convolutional codes calls for Viterbi decodings to be performed for all different pairs of identical starting and terminating encoder states (the number of decodings typically being equal to the number of states of the code) to determine the best path through the trellis satisfying the constraint of identical starting and terminating states.
Such optimum maximum-likelihood decoding requires a great deal of computational resources, and Cox and Sundberg proposed, as an alternative, a class of efficient suboptimum decoding algorithms which reduce the computational burden incurred by the Viterbi decodings for tailbiting convolutional codes. See, for example, the article titled "An Efficient Adaptive Circular Viterbi Algorithm for Decoding Generalized Tailbiting Convolutional Codes", IEEE Transactions on Vehicular Technologies, vol. 43, pp. 57-68, February 1994. This class, collectively referred to as the Cox-Sundberg algorithms, is disclosed in U.S. Pat. No. 5,355,376, issued on Oct. 11, 1994. Generally, according to a Cox-Sundberg algorithm, a received block of coded symbols is conceptually seen as being transmitted repeatedly in block form. Standard continuous Viterbi decoding is performed in a logically circular sequence, stopping in response to an indication from any one of the so-called Viterbi update stopping rules invoked when it is likely that further decoding will not aid in the decoding decision process.
Also known in the art is a group of extended Viterbi algorithms referred to as the List Viterbi algorithms. Whereas the Viterbi algorithm first described above (hereinafter referred to as the "regular" Viterbi algorithm) identifies the single best path through the trellis, a List Viterbi algorithm identifies the L best paths or L best candidates though the trellis. (The case in which L=1 is the standard Viterbi algorithm.) Versions of the List Viterbi algorithms produce a rank ordered list of the L best candidate decodings corresponding to a frame or block of convolutional coded data. See, for example, U.S. Pat. No. 5,208,816, issued May 4, 1993 to Seshadri and Sundberg, and U.S. Pat. No. 5,537,444 issued Jul. 16, 1996 to Nill and Sundberg. List Viterbi algorithms have been found to be advantageous for error detection/correction for convolutionally encoded data and, in particular, have been found to be effective in reducing error flag rates for digital audio broadcasting applications.
List Viterbi algorithms known in the art were designed for block-by-block transmission. In order to find the L best candidates corresponding to a data block, the List Viterbi algorithms require that the decoder must know the state of the encoder when the block encoding commenced (the starting state) and the encoder state when the block encoding terminated (the terminating state).
Although a starting state known to the decoder is easy to achieve, ensuring a known terminating state typically requires that the block of data be terminated with a number of additional known bits, referred to as a tail. Such data is said to have been blockwise terminated with a tail. Disadvantageously, however, the tail represents overhead, for example in terms of wasted bandwidth.
It is desirable to be able to obtain the advantages of using a List Viterbi algorithm to decode blocks of information without incurring the overhead of a tail. Disclosed in our co-pending, commonly-assigned application titled "List Viterbi Algorithms for Continuous Data Transmission", app. Ser. No. 09/055,082, filed of even date herewith is the application of a List Viterbi algorithm for decoding blocks or frames of information which have not been blockwise terminated with a tail. This approach could also be used to decode blocks of information that have been encoded using tailbiting convolutional codes. Such an arrangement, however, would incur the complexity in the transmitter represented by tailbiting without gaining any compensating benefit.